package pro.softzhang.algo.lc100;

import java.util.List;

public class LC120_Triangle {
    public static void main(String[] args) {

    }

    static class Solution {
        public int minimumTotal(List<List<Integer>> triangle) {
            int[] dp = new int[triangle.size()];
            for (List<Integer> row : triangle) {
                for (int j = row.size() - 1; j >= 0; j--) {
                    if(j == 0)
                        dp[j] += row.get(j);
                    else if (j == row.size() - 1)
                        dp[j] = dp[j - 1] + row.get(j);
                    else
                        dp[j] = Math.min(dp[j], dp[j - 1]) + row.get(j);
                }
            }
            int min = Integer.MAX_VALUE;
            for (int num : dp)
                min = Math.min(min, num);
            return min;
        }
    }
}
